use crate::utils::thread_pool::MultiThreadTester;
use std::fmt::Debug;
use std::ptr;
use std::ptr::{null, null_mut};
use std::sync::atomic::Ordering::{AcqRel, Acquire, Relaxed, Release, SeqCst};
use std::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
use std::sync::Arc;

/// atomic 的内存操作顺序控制
/// Relaxed => totally free                                                                     |none
/// Release => any load/store operation must be done before atomic stored                       |load->load
/// Acquire => any load/store operation must be done after atomic loaded                        |store->store
/// AcqRel => with both limitation of Acquire and Release                                       |load->store
/// SeqCst => with the limitation of AcqRel and guaranteed to be visible by all other threads   |store->load
/// 用原生rust库实现一个基于CAS的无锁队列
type NodePtr<T> = AtomicPtr<Node<T>>;
#[derive(Debug)]
struct Node<T> {
    item: Option<T>,
    next: NodePtr<T>,
}

impl<T> Node<T> {
    pub fn new(item: T) -> Self {
        Self {
            item: Some(item),
            next: AtomicPtr::new(null_mut()),
        }
    }
    pub fn new_empty() -> Self {
        Self {
            item: None,
            next: AtomicPtr::new(null_mut()),
        }
    }
}
/// implementing a LinkedQueue can be safely used in multi thread environment
/// however UAF and ABA problem still remains to be solved!!!
#[derive(Debug)]
pub struct LinkedQueue<T> {
    ///thread-safe variable len
    len: AtomicUsize,
    head: NodePtr<T>,
    tail: NodePtr<T>,
}

impl<T> Default for LinkedQueue<T> {
    fn default() -> Self {
        let ptr = Box::into_raw(Box::new(Node::new_empty()));
        Self {
            len: AtomicUsize::new(0),
            head: AtomicPtr::new(ptr),
            tail: AtomicPtr::new(ptr),
        }
    }
}

impl<T> LinkedQueue<T> {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn is_empty(&self) -> bool {
        self.len.compare_exchange(0, 0, Release, Relaxed).is_ok()
    }

    ///use tail insertion
    pub fn push(&self, item: T) {
        let new_node_ptr = Box::into_raw(Box::new(Node::new(item)));
        ///enable old_tail visible by other threads
        let old_tail = self.tail.load(Acquire);
        unsafe {
            let mut old_tail_next_ptr = &(*old_tail).next;
            while old_tail_next_ptr
                .compare_exchange(null_mut(), new_node_ptr, Release, Relaxed)
                .is_err()
            {
                ///failed means tail has been changed by other threads, try to iter and find the true tail
                let mut changed_tail_next = old_tail_next_ptr.load(Acquire);
                loop {
                    let next = (*changed_tail_next).next.load(Acquire);
                    if next.is_null() {
                        break;
                    }
                    changed_tail_next = next;
                }
                old_tail_next_ptr = &(*changed_tail_next).next;
            }
            ///if success
            let _ = self
                .tail
                .compare_exchange(old_tail, new_node_ptr, Release, Relaxed);
            self.len.fetch_add(1, SeqCst);
        }
    }
    /// pop data from head of queue
    pub fn pop(&self) -> Option<T> {
        let mut data = None;
        if self.is_empty() {
            return data;
        }
        unsafe {
            let mut head;
            loop {
                head = self.head.load(Acquire);
                let next = (*head).next.load(Acquire);
                if next.is_null() {
                    return None;
                }
                if self
                    .head
                    .compare_exchange(head, next, Release, Relaxed)
                    .is_ok()
                {
                    data = (*next).item.take();
                    break;
                }
            }
            let _ = Box::from_raw(head);
        }

        self.len.fetch_sub(1, SeqCst);
        data
    }
}

fn print_queue<T: Debug>(queue: &LinkedQueue<T>) {
    unsafe {
        let mut index = (*queue.head.load(Relaxed)).next.load(Relaxed);
        loop {
            if index.is_null() {
                break;
            }
            if let Some(item) = &(*index).item {
                print!("{:#?}->", item);
            }
            index = (*index).next.load(Relaxed);
        }
        print!("null");
        println!();
    }
}

#[test]
fn test_linked_queue() {
    let queue = Arc::new(LinkedQueue::<i32>::default());
    let th_queue1 = queue.clone();
    let th_queue2 = queue.clone();
    let mut tester = MultiThreadTester::new();
    tester
        .append_test(
            "queue",
            move || {
                // let _ = th_lock1.lock().unwrap();
                th_queue1.push(1);
            },
            10000,
        )
        .append_test(
            "what",
            move || loop {
                if !th_queue2.is_empty() {
                    if let Some(_) = th_queue2.pop(){
                        break;
                    }
                }
            },
            400,
        )
    ;
    tester.run();
    println!("{}", queue.len.load(Acquire));
}
